{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Combination Sum IV"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #dynamic-programming"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #动态规划"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: combinationSum4"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #组合总和 Ⅳ"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个由 <strong>不同</strong> 整数组成的数组 <code>nums</code> ，和一个目标整数 <code>target</code> 。请你从 <code>nums</code> 中找出并返回总和为 <code>target</code> 的元素组合的个数。</p>\n",
    "\n",
    "<p>题目数据保证答案符合 32 位整数范围。</p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [1,2,3], target = 4\n",
    "<strong>输出：</strong>7\n",
    "<strong>解释：</strong>\n",
    "所有可能的组合为：\n",
    "(1, 1, 1, 1)\n",
    "(1, 1, 2)\n",
    "(1, 2, 1)\n",
    "(1, 3)\n",
    "(2, 1, 1)\n",
    "(2, 2)\n",
    "(3, 1)\n",
    "请注意，顺序不同的序列被视作不同的组合。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [9], target = 3\n",
    "<strong>输出：</strong>0\n",
    "</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 <= nums.length <= 200</code></li>\n",
    "\t<li><code>1 <= nums[i] <= 1000</code></li>\n",
    "\t<li><code>nums</code> 中的所有元素 <strong>互不相同</strong></li>\n",
    "\t<li><code>1 <= target <= 1000</code></li>\n",
    "</ul>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>进阶：</strong>如果给定的数组中含有负数会发生什么？问题会产生何种变化？如果允许负数出现，需要向题目中添加哪些限制条件？</p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [combination-sum-iv](https://leetcode.cn/problems/combination-sum-iv/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [combination-sum-iv](https://leetcode.cn/problems/combination-sum-iv/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,2,3]\\n4', '[9]\\n3']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum4(self, nums: List[int], target: int) -> int:\n",
    "        nums.sort()\n",
    "\n",
    "        @functools.lru_cache(maxsize = None)#对于函数的注解\n",
    "        def combs(remain):\n",
    "            if remain == 0:\n",
    "                return 1\n",
    "            \n",
    "            result = 0\n",
    "            for num in nums:\n",
    "                if remain - num >= 0:\n",
    "                    result += combs(remain - num)\n",
    "                else:\n",
    "                    break\n",
    "            return result\n",
    "        \n",
    "        return combs(target)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum4(self, nums, target):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :type target: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        # n = len(nums)\n",
    "        \n",
    "        f = [0] * (target+1)\n",
    "        f[0] = 1\n",
    "        \n",
    "        for i in range(1,target+1):\n",
    "            for j in nums:\n",
    "                if j<=i:\n",
    "                    f[i] += f[i-j]\n",
    "        return f[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum4(self, nums, target):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :type target: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        mem = [int(0)  for i in range(target+1)]\n",
    "        mem[0] = 1\n",
    "        for i in range(1,target+1):\n",
    "            for j in nums:\n",
    "                if i >= j:\n",
    "                    mem[i] = mem[i] + mem[i-j]\n",
    "        return mem[target]\n",
    "                \n",
    "                \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum4(self, nums, target):\n",
    "        dp = [1]\n",
    "        nums.sort()\n",
    "        for i in range(1, target + 1):\n",
    "            dp.append(0)\n",
    "            for j in nums:\n",
    "                if j <= i:\n",
    "                    dp[-1] += dp[i - j]\n",
    "                else:\n",
    "                    break\n",
    "        return dp[-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # 动态规划法\n",
    "    def combinationSum4(self, nums, target):\n",
    "        dp = collections.defaultdict(int)\n",
    "        dp[0] = 1\n",
    "        for i in range(target + 1):\n",
    "            for num in nums:\n",
    "                if i - num >= 0:\n",
    "                    dp[i] += dp[i - num]\n",
    "        return dp[target]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum4(self, nums, target):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :type target: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        from collections import defaultdict\n",
    "        dp, nums = defaultdict(int), sorted(nums)\n",
    "        for num in nums:\n",
    "            dp[num] = 1\n",
    "        for loop in range(2, target + 1):\n",
    "            for num in nums:\n",
    "                dp[loop] += dp[loop - num]\n",
    "        return dp[target]            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum4(self, nums, target):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :type target: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        #如果数组中没有元素，显然就不能组合成任何target\n",
    "        if len(nums)==0:\n",
    "            return 0\n",
    "\n",
    "        self.dp=[-1]*(target+1)\n",
    "        self.dfs(nums,target)\n",
    "        # print(self.dp)\n",
    "        return self.dp[-1]\n",
    "\n",
    "    def dfs(self,nums,target):\n",
    "\n",
    "        if target==0:\n",
    "            return 1\n",
    "\n",
    "        if self.dp[target]!=-1:\n",
    "            return self.dp[target]\n",
    "\n",
    "        res=0\n",
    "        for i in range(0,len(nums)):\n",
    "            \n",
    "            if nums[i]<=target:\n",
    "                res+=self.dfs(nums,target-nums[i])\n",
    "\n",
    "        self.dp[target]=res         #存储结果\n",
    "        return res              #返回结果\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.me = []\n",
    "    def combinationSum4(self, nums: 'List[int]', target: 'int') -> 'int':\n",
    "        if not nums or target < 1:\n",
    "            return 0\n",
    "        self.me = [-1 for i in range(target+1)]\n",
    "        res = self.help(nums, target, [])\n",
    "        return res\n",
    "    def help(self, nums, target, ans):\n",
    "        if target == 0:\n",
    "            return 1\n",
    "        if self.me[target] != -1:\n",
    "            return self.me[target]\n",
    "        res = 0\n",
    "        for i in nums:\n",
    "            if i <= target:\n",
    "                res += self.help(nums, target-i, ans)\n",
    "        self.me[target] = res\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum4(self, nums, target):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :type target: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        nums.sort()\n",
    "        self.cache = {}\n",
    "        self.n = nums\n",
    "        return self.helper(target)\n",
    "    \n",
    "    def helper(self, target):\n",
    "        if target in self.cache:\n",
    "            return self.cache[target]\n",
    "        res = 0\n",
    "        for i in self.n:\n",
    "            if i > target:\n",
    "                break\n",
    "            elif i == target:\n",
    "                res += 1\n",
    "            else:\n",
    "                res += self.helper(target - i)\n",
    "        self.cache[target] = res\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum4(self, nums: 'List[int]', target: 'int') -> 'int':\n",
    "        \n",
    "        def comb_(nums, target, dp):\n",
    "            if dp[target] >= 0:\n",
    "                return dp[target]\n",
    "            c = 0\n",
    "            for i in nums:\n",
    "                if i > target:\n",
    "                    break\n",
    "                c += comb_(nums, target - i, dp)\n",
    "            dp[target] = c\n",
    "            return c\n",
    "        \n",
    "        dp = [-1] * (target + 1)\n",
    "        dp[0] = 1\n",
    "        nums.sort()\n",
    "        return comb_(nums, target, dp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum4(self, nums, target):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :type target: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        \n",
    "        nums = sorted(nums)\n",
    "        cals = {}\n",
    "        def dfs(t):\n",
    "            ans = 0\n",
    "            if t == 0:\n",
    "                return 1\n",
    "            if t in cals:\n",
    "                return cals[t]\n",
    "            for n in nums:\n",
    "                if t-n < 0:\n",
    "                    break\n",
    "                ans += dfs(t-n)\n",
    "            cals[t] = ans\n",
    "            return ans\n",
    "        return dfs(target)\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def combinationSum4(self, nums: List[int], target: int) -> int:\r\n",
    "        if len(nums) == 0: return 0\r\n",
    "        dp = [0] * (target + 1)\r\n",
    "        dp[0] = 1\r\n",
    "        for x in range(1, target + 1):\r\n",
    "            for num in nums:\r\n",
    "                if x - num >= 0:\r\n",
    "                    dp[x] += dp[x-num]\r\n",
    "        return dp[target]\r\n",
    "                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum4(self, nums: List[int], target: int) -> int:\n",
    "        size = len(nums)\n",
    "        if size == 0 or target <= 0:\n",
    "            return 0\n",
    "\n",
    "        dp = [0 for _ in range(target + 1)]\n",
    "        \n",
    "        # 这一步很关键，想想为什么 dp[0] 是 1\n",
    "        # 因为 0 表示空集，空集和它\"前面\"的元素凑成一种解法，所以是 1\n",
    "        # 这一步要加深体会\n",
    "        \n",
    "        dp[0] = 1\n",
    "\n",
    "        for i in range(1, target + 1):\n",
    "            for j in range(size):\n",
    "                if i >= nums[j]:\n",
    "                    dp[i] += dp[i - nums[j]]\n",
    "\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from copy import deepcopy\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum4(self, nums: List[int], target: int) -> int:\n",
    "        size = len(nums)\n",
    "        if size == 0 or target <= 0:\n",
    "            return 0\n",
    "\n",
    "        dp = [0 for _ in range(target + 1)]\n",
    "        \n",
    "        # 这一步很关键，想想为什么 dp[0] 是 1\n",
    "        # 因为 0 表示空集，空集和它\"前面\"的元素凑成一种解法，所以是 1\n",
    "        # 这一步要加深体会\n",
    "        \n",
    "        dp[0] = 1\n",
    "\n",
    "        for i in range(1, target + 1):\n",
    "            for j in range(size):\n",
    "                if i >= nums[j]:\n",
    "                    dp[i] += dp[i - nums[j]]\n",
    "\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum4(self, nums: List[int], target: int) -> int:\n",
    "        if not nums:\n",
    "            return 0\n",
    "        dp = [0] * (target+1)\n",
    "        dp[0] = 1\n",
    "        for i in range(1,target+1):\n",
    "            for num in nums:\n",
    "                if i >= num:\n",
    "                    dp[i] += dp[i-num]\n",
    "        return dp[target]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum4(self, nums: List[int], target: int) -> int:\n",
    "        # import functools\n",
    "\n",
    "        # @functools.lru_cache(None)\n",
    "        # def back(tmp):\n",
    "        #     if tmp==target:\n",
    "        #         return 1\n",
    "        #     ans=0\n",
    "        #     for i in range(len(nums)):\n",
    "        #         val=tmp+nums[i]\n",
    "        #         if val>target:continue\n",
    "        #         ans+=back(val)\n",
    "        #     return ans\n",
    "\n",
    "        # return back(0)\n",
    "\n",
    "        dp=[0]*(target+1)\n",
    "        dp[0]=1\n",
    "        for i in range(1,target+1):\n",
    "            for j in range(len(nums)):\n",
    "                if i>=nums[j]:\n",
    "                    dp[i]+=dp[i-nums[j]]\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    \n",
    "    count = []\n",
    "    def combinationSum4(self, nums: List[int], target: int) -> int:\n",
    "        dp = [0 for i in range(target + 1)]\n",
    "        dp[0] = 1\n",
    "        for t in range(target + 1):\n",
    "            for n in nums:        \n",
    "                if n <= t:\n",
    "                    dp[t] += dp[t - n]\n",
    "        return dp[target]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum4(self, nums: List[int], target: int) -> int:\n",
    "        dp = [0] * (target+1)\n",
    "        dp[0] = 1\n",
    "        for i in range(1, target+1):\n",
    "            for num in nums:\n",
    "                if i >= num:\n",
    "                    dp[i] += dp[i-num]\n",
    "\n",
    "        return dp[-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum4(self, nums: List[int], target: int) -> int:\n",
    "        size = len(nums)\n",
    "        if size == 0 or target <= 0:\n",
    "            return 0\n",
    "\n",
    "        dp = [0 for _ in range(target + 1)]\n",
    "        \n",
    "        # 这一步很关键，想想为什么 dp[0] 是 1\n",
    "        # 因为 0 表示空集，空集和它\"前面\"的元素凑成一种解法，所以是 1\n",
    "        # 这个值被其它状态参考，设置为 1 是合理的\n",
    "        \n",
    "        dp[0] = 1\n",
    "\n",
    "        for i in range(1, target + 1):\n",
    "            for j in range(size):\n",
    "                if i >= nums[j]:\n",
    "                    dp[i] += dp[i - nums[j]]\n",
    "\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum4(self, nums: List[int], target: int) -> int:\n",
    "        from collections import defaultdict\n",
    "        if not nums:\n",
    "            return 0\n",
    "        dp = defaultdict(int)\n",
    "        dp[0] = 1\n",
    "        for i in range(1, target + 1):\n",
    "            res = 0\n",
    "            for num in nums:\n",
    "                if i >= num:\n",
    "                    res += dp[i - num]\n",
    "            dp[i] = res\n",
    "        \n",
    "        # print(dp)\n",
    "        return dp[target]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum4(self, nums: List[int], target: int) -> int:\n",
    "        #回溯算法(超出内存限制)\n",
    "        # result = []\n",
    "        # def helper(tmp):\n",
    "        #     if sum(tmp) == target:\n",
    "        #         result.append(tmp)\n",
    "        #         return\n",
    "        #     if sum(tmp) > target:\n",
    "        #         return\n",
    "        #     for i in range(len(nums)):\n",
    "        #         tmp.append(nums[i])\n",
    "        #         helper(tmp[:])\n",
    "        #         tmp.pop()\n",
    "        # helper([])\n",
    "        # return len(result)\n",
    "\n",
    "        #因为返回的是数量，所以可以用动态规划求解\n",
    "        dp = [0]*(target+1)\n",
    "\n",
    "        dp[0] = 1\n",
    "        for i in range(1,target+1):\n",
    "            for num in nums:\n",
    "                if i - num < 0:\n",
    "                    continue\n",
    "                dp[i] += dp[i-num]\n",
    "        print(dp)\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum4(self, nums: List[int], target: int) -> int:\n",
    "        dp = [0 for _ in range(target + 1)]\n",
    "        dp[0] = 1\n",
    "        for j in range(target + 1):\n",
    "            for i in range(len(nums)):\n",
    "                if j >= nums[i]: dp[j] += dp[j - nums[i]]\n",
    "        return dp[target]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum4(self, nums: List[int], target: int) -> int:\n",
    "        dp=[0]*(target+1)\n",
    "        dp[0] =1\n",
    "        for j in range(target+1):\n",
    "            for num in nums:\n",
    "                if num <=j:\n",
    "                    dp[j] = dp[j]+dp[j-num]\n",
    "        return dp[target]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum4(self, nums: List[int], target: int) -> int:\n",
    "        n = len(nums)\n",
    "        dp = [1] + [0] * target\n",
    "        for v in range(1, target+1):\n",
    "            for num in nums:\n",
    "                if num <= v:\n",
    "                    dp[v] += dp[v-num]\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def combinationSum4(self, nums: List[int], target: int) -> int:\r\n",
    "        dp = [1] + [0] * target\r\n",
    "        for i in range(1, target + 1):\r\n",
    "            for num in nums:\r\n",
    "                if num <= i:\r\n",
    "                    dp[i] += dp[i - num]\r\n",
    "        return dp[target]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum4(self, nums: List[int], target: int) -> int:\n",
    "        @cache\n",
    "\n",
    "        def dp(target):\n",
    "            if target == 0:\n",
    "                return 1\n",
    "            if target < 0:\n",
    "                return 0\n",
    "\n",
    "            total = 0\n",
    "            for n in nums:\n",
    "                total += dp(target-n)\n",
    "\n",
    "            return total\n",
    "        return dp(target)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum4(self, nums: List[int], target: int) -> int:\n",
    "        dp = [0] * (target+1)\n",
    "        dp[0] = 1\n",
    "        for j in range(target+1):\n",
    "            for num in nums:\n",
    "                if j >= num:\n",
    "                    dp[j] += dp[j-num]\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum4(self, nums: List[int], target: int) -> int:\n",
    "        # dp = [0]*(target+1)\n",
    "        # dp[0] = 1\n",
    "        # for i in range(target+1):\n",
    "        #     for num in nums:\n",
    "        #         if i>=num:\n",
    "        #             dp[i]+=dp[i-num]\n",
    "        # return dp[-1]\n",
    "        n=len(nums)\n",
    "        dp=[0]*(target+1)\n",
    "        dp[0]=1\n",
    "        for i in range(target+1):\n",
    "            for num in nums:\n",
    "                if i>=num:\n",
    "                    dp[i]+=dp[i-num]\n",
    "            \n",
    "        return dp[-1]\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum4(self, nums: List[int], target: int) -> int:\n",
    "\n",
    "\n",
    "        #dp[i] 综合为i的元素组合的个数\n",
    "\n",
    "        dp = [0] * (target + 1)\n",
    "        dp[0] = 1\n",
    "        for i in range(1, target + 1):\n",
    "            for j in range(0, len(nums)):\n",
    "                if i >= nums[j]:\n",
    "                    dp[i] += dp[i - nums[j]]\n",
    "        return dp[-1]\n",
    "        \n",
    "        # for i in range(1, len(nums)):\n",
    "        #     for j in range(nums[i], target + 1):\n",
    "        #         dp[j] += dp[j - nums[i]] * dp[nums[i]]\n",
    "        #     print(dp)\n",
    "        # return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum4(self, nums: List[int], target: int) -> int:\n",
    "        \n",
    "        # 定义状态，dp[i] 组合总和为 i 时组合的个数，因为可以取到target，所以长度为target+1，初始化dp[0]=1或全为1\n",
    "        dp = [0] * (target + 1)\n",
    "        dp[0] = 1\n",
    "        \n",
    "        for i in range(1, target + 1):\n",
    "            for num in nums:\n",
    "                if num <= i:\n",
    "                    dp[i] += dp[i-num]\n",
    "        return dp[target]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum4(self, nums: List[int], target: int) -> int:\n",
    "        @cache\n",
    "        def f(i: int):\n",
    "            if i == 0:\n",
    "                return 1\n",
    "            return sum(f(i - n) for n in nums if i - n >= 0)\n",
    "\n",
    "        return f(target)"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
